#include "pqueue.h"
#include "genlib.h"

struct pqueueCDT {
	edgeT *arr;
	int nElements;
	int currentSize;
};

static void swapElements(edgeT arr[], int element1, int element2);
static void increaseMaxArraySize(pqueueADT pqueue);
static void printTree(pqueueADT pqueue);

/* Exported endries */

pqueueADT NewPQueue(void){
	pqueueADT pqueue;

	pqueue = New(pqueueADT);
	pqueue->currentSize = 33;
	pqueue->nElements = 1;
	pqueue->arr = NewArray(pqueue->currentSize, edgeT);
	return (pqueue);
}

void FreePQueue(pqueueADT pqueue){
	FreeBlock(pqueue);
}

bool IsEmpty(pqueueADT pqueue){
	return (pqueue->nElements == 1);
}

bool IsFull(pqueueADT pqueue){
	return (FALSE);
}

void Enqueue(pqueueADT pqueue, edgeT newValue){
	int newValuePos;

	if (pqueue->currentSize <= pqueue->nElements) 
		increaseMaxArraySize(pqueue);

	pqueue->arr[pqueue->nElements] = newValue;

	if(pqueue->nElements > 1){
		newValuePos = pqueue->nElements;
		while(pqueue->arr[newValuePos].value < pqueue->arr[newValuePos/2].value){
			swapElements(pqueue->arr, newValuePos, newValuePos/2);
			newValuePos = newValuePos/2;
			if(newValuePos <= 1) break;
		}
	}
	pqueue->nElements++;
}

static void increaseMaxArraySize(pqueueADT pqueue){
	int i;
	edgeT *newArr = NewArray(((pqueue->currentSize-1)*2)+1, edgeT);
	for(i = 1; i < pqueue->nElements; i++)
		newArr[i] = pqueue->arr[i];
	pqueue->arr = newArr;
	pqueue->currentSize *= 2;
}

static void swapElements(edgeT arr[], int element1, int element2){
	edgeT temp;

	temp = arr[element1];
	arr[element1] = arr[element2];
	arr[element2] = temp;
}

edgeT DequeueMin(pqueueADT pqueue){
	int newValuePos, biggestChildPos;
	edgeT ret;

	if (IsEmpty(pqueue))
		Error("Tried to dequeue max from an empty pqueue!");

	ret = pqueue->arr[1];

	swapElements(pqueue->arr, 1, pqueue->nElements-1);
	pqueue->nElements--;
	
	newValuePos = 1;

	while(TRUE){
		if((newValuePos*2)+1 < pqueue->nElements){
			if(pqueue->arr[(newValuePos*2)].value >= pqueue->arr[newValuePos].value && pqueue->arr[(newValuePos*2)+1].value >= pqueue->arr[newValuePos].value){
				break;
			}
			else if(pqueue->arr[(newValuePos*2)+1].value < pqueue->arr[(newValuePos*2)].value){
				biggestChildPos = (newValuePos*2)+1;
			}else{
				biggestChildPos = newValuePos*2;
			}
			swapElements(pqueue->arr, biggestChildPos, newValuePos);
			newValuePos = biggestChildPos;
		}
		else if(newValuePos*2 < pqueue->nElements){
			if(pqueue->arr[newValuePos*2].value < pqueue->arr[newValuePos].value){

				swapElements(pqueue->arr, newValuePos*2, newValuePos);
				newValuePos = newValuePos*2;
			}
			break;
		}
		else 
			break;
	}
	return (ret);
}

int BytesUsed(pqueueADT pqueue){
	return (pqueue->currentSize*sizeof(int));
}